【REOI2020R1】rui_er的水题大赛赛后题解&总结

文章同步发布于洛谷博客

1 赛后总结与奖项公示

封榜统计时排名(截图):

比赛报名选手:87 人。

有提交记录选手:18 人。

AK选手:1 人。

下面为奖项统计。

1.1 全场首A

恭喜 @wzm2007 获得全场首A,赢得¥0.3!

1.2 每题首A

恭喜 @wzm2007 获得A题首A,赢得¥0.1!

恭喜 @henrytb 获得B题首A,赢得¥0.1!

恭喜 @henrytb 获得C题首A,赢得¥0.1!

恭喜 @henrytb 获得D题首A,赢得¥0.1!

恭喜 @henrytb 获得E题首A,赢得¥0.1!

恭喜 @henrytb 获得F题首A,赢得¥0.1!

1.3 全场AK与奖励补足

恭喜 @henrytb 获得全场AK,赢得¥0.5!

AK人数补足,剩余两个奖励名额按照规则顺延,恭喜 @AC_Automation 和 @happydef 获得顺延奖励每人¥0.5!

1.4 BC最优解

由于B题只有 @henrytb AC,恭喜他获得最优解,赢得¥0.2!

由于C题只有 @henrytb AC,恭喜他获得最优解,赢得¥0.2!

1.5 幸运奖

从全场有提交记录选手中随机抽取,恭喜 @蒟蒻跟风侠 赢得¥0.3!

1.6 赛后新增奖项

1.6.1 爆踩std

由于 @henrytb 六道题全部AC并且程序全部爆踩std,rui_er决定给予特别奖励¥0.2!

1.6.2 幸运奖-2

由于rui_er认为只设置一个幸运奖有点少,于是设立了幸运二等奖(¥0.2),恭喜 @拥抱渴望者 赢得¥0.2!

请上述获奖选手于 2020 年 4 月 15 日前私信 rui_er 微信号,或者付款二维码,逾期奖项自动作废!

2 赛后题解

2.1 A题

题目描述

U2FsdGVkX1/PKGHGgf9gxZXO3tzmWSQUM5hO/Z+TEB63Oj0VR9TUPO/BAbCEHnUQ13gJFWJEDZOCh8QEsHcTtw6P+yqP9uoNHOx1k08N7t/twwyV2X009ZyryU2cJjiBAiHvfOmyRkF2PoOYIaYVVIYJINEoaxQxOQym7MWilN0adltSu56agfKQeZOLd2ye0Cpe332weyDPUpVUeQ++EY7jRSz3AOjY+kEAuAwx3npxAp4DuX4eu5VZz6xdhQ==

显然是一串密文,利用加密解密工具多试几次,发现是RC4加密。可以解密出明文:

Long long ago, there is a DALAO called rui_er. He is young, but he always AK IOI. Sometimes he also dd jxd. He is so powerful that most OIers AFO because of him. Let's % him!

输出即可。

2.2 B题

使用工具画出函数图像,并列举前几个数找规律:

数列 0, 1, 6, 21, 55, 120

差分 ~, 1, 5, 15, 34, 65

差分 ~, ~, 4, 10, 19, 31

差分 ~, ~, ~, 6, 9, 12

差分 ~, ~, ~, ~, 3, 3

规律就出来了,很明显,不是吗?

代码:

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1000001;

long long a[MAXN] = {0, 1, 6, 21, 55, 120}, b[MAXN] = {0, 1, 5, 15, 34, 65}, c[MAXN] = {0, 0, 4, 10, 19, 31}, d[MAXN] = {0, 0, 0, 6, 9, 12};
vector<long long> v;

int main()
{
	long long l, r;
	cin>>l>>r;
	for(long long i=1;i<=r;i++) 
	{
		if(i <= 5 && i >= l)
		{
			v.push_back(a[i]);
			continue;
		}
		else if(i <= 5) continue;
		d[i] = (d[i-1] + 3) % 998244353;
		c[i] = (c[i-1] + d[i]) % 998244353;
		b[i] = (b[i-1] + c[i]) % 998244353;
		a[i] = (a[i-1] + b[i]) % 998244353;
		if(i >= l) v.push_back(a[i]);
	}
	cout<<v.size()<<endl;
	for(int i=0;i<v.size();i++) cout<<v[i]<<" ";
	cout<<endl;
	return 0;
}

当然你也可以打表。

2.3 C题

珂朵莉树板子题,切了切了~

不会珂朵莉树的点这里,想练习珂朵莉树的点这里

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353LL;
const ll MAXN = 100001;

ll n, m, seed, ans;
ll a[MAXN];
struct Node
{
	ll l, r;
	mutable ll v;
	Node(ll x, ll y = -1, ll z = 0): l(x), r(y), v(z) {}
	bool operator < (const Node &a) const {return l < a.l;}
};
typedef set<Node>::iterator IT;
set<Node> ODT;

ll rnd() 
{
	ll ret = seed;
	seed = (seed * 5 + 2) % mod;
	return ret;
}

IT split(ll pos)
{
	IT iter = ODT.lower_bound(Node(pos));
	if(iter != ODT.end() && iter->l == pos) return iter;
	--iter;
	ll L = iter->l, R = iter->r, V = iter->v;
	ODT.erase(iter);
	ODT.insert(Node(L, pos-1, V));
	return ODT.insert(Node(pos, R, V)).first;
}

void upd1(ll l, ll r, ll dt)
{
	IT iterR = split(r+1), iterL = split(l);
	for(iterL;iterL!=iterR;++iterL) iterL->v *= dt;
}

void upd2(ll l, ll r)
{
	IT iterR = split(r+1), iterL = split(l);
	for(iterL;iterL!=iterR;++iterL) iterL->v = sqrt(iterL->v);
}

ll kth(ll l, ll r, ll k)
{
	vector<pair<ll, ll> > v;
	IT iterR = split(r+1), iterL = split(l);
	for(iterL;iterL!=iterR;++iterL) v.push_back(make_pair(iterL->v, iterL->r-iterL->l+1));
	sort(v.begin(), v.end());
	for(vector<pair<ll, ll> >::iterator iter=v.begin();iter!=v.end();++iter)
	{
		k -= iter->second;
		if(k <= 0) return iter->first;
	}
}

void assign_val(ll l, ll r, ll w)
{
	IT iterR = split(r+1), iterL = split(l);
	ODT.erase(iterL, iterR);
	ODT.insert(Node(l, r, w));
}

int main()
{
	scanf("%lld%lld%lld", &n, &m, &seed);
	for(ll i=1;i<=n;i++)
	{
		scanf("%lld", &a[i]);
		ODT.insert(Node(i, i, a[i]));
	}
	for(ll i=1;i<=m;i++)
	{
		ll op = rnd() % 4 + 1;
		ll l = rnd() % n + 1;
		ll r = rnd() % n + 1;
		if(l > r) swap(l, r);
		ll k;
		if(op == 1 || op == 2) k = rnd() % 5 + 1;
		else if(op == 3) k = rnd() % (r - l + 1) + 1;
		else k = rnd();
		if(op == 1) upd1(l, r, k);
		else if(op == 2) upd2(l, r);
		else if(op == 3) ans ^= kth(l, r, k);
		else assign_val(l, r, k);
	}
	printf("%lld\n", ans);
	return 0;
}

2.4 D题

打开F12,发现题目描述“无”后面有个指向A+B Problem的链接,因为内容是空的,所以看不到。此题就是A+B,注意到数据范围写着数据范围*=2,会爆int,记得开long long。

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;

long long a, b;

int main()
{
	cin>>a>>b;
	cout<<a+b<<endl;
	return 0;
}

2.5 E题

E题是一道高中物理题,不会那也没办法了QwQ。第一问根据公式送分 Ep=mghE_p=mgh。第二问根据公式 h=12gt2h=\frac{1}{2}gt^2,可得 t=2.0×hgt=\sqrt{\frac{2.0\times h}{g}},所以 v=gt=g2.0×hgv=gt=g\sqrt{\frac{2.0\times h}{g}}

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;

int main()
{
	double g, h, m;
	cin>>g>>h>>m;
	double w = m * g * h;
	double v = g * sqrt(2.0*h/g);
	cout<<setprecision(4)<<fixed<<w<<" "<<v<<endl;
	return 0;
}

2.6 F题

F12发现“祝你成功AK”后面有个链接,点进去发现什么也没有。真的什么也没有吗?想起nazo中有一关“goL elosnoC uhihZ”,于是打开F12,进入“控制台”(英文版本叫“Console”),发现answer:rui_er txdy,输出rui_er txdy即可。